Motion estimation techniques play an integral role in video compression and processing applications. As an example, scan rate up-conversion is a common feature implemented by many televisions. A number of modern televisions support frame rates up to 120 frames per second (fps), while the incoming signal may be represented at a lower frame rate. For example, many cable broadcasts include a signal at a native rate of 60 fps. Through the use of motion estimation and motion compensation techniques, a television may receive a 60 fps signal, but output a 240 fps display, thereby increasing clarity and reducing motion artifacts. In other words, by applying these techniques to the incoming frames, the television may interpolate 60 additional frames per second to fill in the gaps.
With the advent of high definition signals and advanced high resolution display technologies, such as Liquid Crystal Display (LCD) and Plasma, the amount of data included in video signals is rapidly increasing. As a corollary, as the amount of data increases, the amount of processing power required to perform real-time motion estimation also increases. Thus, hardware and software designers have given considerable attention to optimizing the algorithms used for motion estimation for real-time applications.
The Three-Dimensional Recursive Search (3DRS) algorithm, described in “True-Motion Estimation with 3-D Recursive Search Block Matching,” by de Haan et al. (incorporated by reference herein) is one of the most widely-used motion estimation methods for applications requiring real-time, cost-effective processing. The 3DRS algorithm is based on block matching, such that a frame is divided into a number of pixel blocks and processing is performed for each such block. For each block, the algorithm calculates a motion vector representing the movement of the corresponding block from the previous frame. In order to determine the motion between frames, the 3DRS algorithm makes two assumptions: (i) objects are larger than a block of pixels; and (ii) objects have inertia. These assumptions suggest that motion in a particular block of pixels is related to motion of the surrounding blocks and that motion in the previous frame can represent motion in the current frame.
Given these assumptions, typical implementations of the 3DRS algorithm must follow a predetermined scanning order, as motion information is only available for the blocks that have already been processed. More specifically, when implementing a meandering scanning order, each block of pixels depends on a previous block of pixels in the same row and a number of blocks in the previously-processed row. These dependencies make it difficult to apply an effective parallelization technique to the algorithm. In other words, current implementations of the 3DRS algorithm are not fully scalable and do not map easily onto multi-core processors.
In view of the foregoing, it would be desirable to implement a parallelized 3DRS meandering motion estimation algorithm that does not compromise picture quality. It would also be desirable to implement a motion estimation device that allows for multi-core execution of the 3DRS motion estimation algorithm. Other desirable aspects will be apparent to those of skill in the art upon reading and understanding the present specification.